// 题目描述：
// 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
// 叶子节点 是指没有子节点的节点。
// 题目链接：https://leetcode.cn/problems/binary-tree-paths/

// 先序递归解决（O(N^2),O(N^2)）
class Solution {
public:
	//思考这里为什么path不使用引用
    void binaryTree(TreeNode* root,vector<string> &vs,string path){
        // 打印当前遍历节点
        path += to_string(root->val);
        // 当前节点是叶子节点就说明一条路径处理完
        if(root->left == nullptr && root->right == nullptr){
            vs.push_back(path);
            return;
        }
        // 当前不是叶子节点，分别处理左右子节点
        if(root->left) binaryTree(root->left,vs,path+"->");
        if(root->right) binaryTree(root->right,vs,path+"->");
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        // 初始化辅助数据
        vector<string> res;
        string path;
        // 节点为空直接输出
        if(root == nullptr) return res;
        // 调用递归打印
        binaryTree(root,res,path);
        return res;
    }
};

// 广度优先（O(N^2),O(N^2)）
// 该方法本质上就是维护一个与遍历节点队列相对应的遍历节点所拥有的路径队列
如对于层序为123的树，其队列改变状态分别为1-->2-->2,3-->3和“1”-->"1->2,1->3"
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        // 初始化结果向量resPath、
        // 保存每个结点的当前路径的quePath，已经节点访问队列queNode
        vector<string> resPath;
        if(root == nullptr) return resPath;
        queue<TreeNode*> queNode;
        queue<string> quePath;
        // 首元素入队，首元素组成的path入队
        queNode.push(root);
        quePath.push(to_string(root->val));
        
        while(!queNode.empty()){
            // 取出两个队首元素分别用于广度遍历和路径更新
            TreeNode* node = queNode.front();
            string path = quePath.front();
            // 弹出队首元素
            queNode.pop();
            quePath.pop();

            //如果已经是叶子节点，那么保存此路径到resParh 
            if(!node->right && !node->left){
                resPath.push_back(path);
            }
            // 否则，继续访问队首元素的子节点并更新路径队列的值
            else{
             if(node->left){
                queNode.push(node->left);
                quePath.push(path+"->"+to_string(node->left->val));
            } 
            if(node->right){
                queNode.push(node->right);
                quePath.push(path+"->"+to_string(node->right->val));
            }   
            }
        }
        return resPath;
    }
};
